package HOT;

/**
 * Author  zxy
 * Date  2023/7/12 10:21
 */

/*
* 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，
* 那么整个数组都会变为升序排序。
* 请你找出符合题意的 最短 子数组，并输出它的长度。
* */

public class FindUnsortedSubarray_74 {
    public int findUnsortedSubarray(int[] nums) {

        int len = nums.length;

        // 一次遍历
        int maxm = Integer.MIN_VALUE;
        int minm = Integer.MAX_VALUE;
        int left = -1;
        int right = -1;

        for (int i = 0; i < len; i++) {
            if (maxm > nums[i]) {
                right = i;
            } else {
                maxm = nums[i];
            }

            if (minm < nums[len - i - 1]) {
                left = len - i - 1;
            } else {
                minm = nums[len - i - 1];
            }
        }

        return right == -1 ? 0 : right - left + 1;


        // 单调栈从前往后遍历一遍可得到左边界
        // 单调栈从后往前遍历一遍可得到右边界
        /*
        Deque<Integer> stack = new ArrayDeque<>();
        int left = nums.length;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }

        stack.clear();
        int right = -1;
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }

        return right - left > 0 ? right - left + 1 : 0;
        */


        // O(nlogn)
        /*
        int[] temp = Arrays.copyOf(nums, len);

        Arrays.sort(nums);

        int left = 0;
        int right = len - 1;

        for (int i = 0; i < len; i++) {
            if (temp[leftv] == nums[i]) {
                left++;
            }
            else {
                break;
            }
        }

        for (int i = len - 1; i >= 0; i--) {
            if (temp[right] == nums[i]) {
                right--;
            }
            else {
                break;
            }
        }

        return right > left ? right - left + 1 : 0;
        */

    }
}

